/*
 * Created on 29-Apr-2005
 * Created by Paul Gardner
 * Copyright (C) Azureus Software, Inc, All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

package com.aelitis.azureus.core.util.bloom.impl;

import java.lang.reflect.Constructor;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

import org.gudy.azureus2.core3.util.Debug;
import org.gudy.azureus2.core3.util.SystemTime;

import com.aelitis.azureus.core.util.bloom.BloomFilter;
import com.aelitis.azureus.util.MapUtils;

public abstract class BloomFilterImpl implements BloomFilter {
    protected static final String MY_PACKAGE = "com.aelitis.azureus.core.util.bloom.impl";

    /*
     * private static final boolean USE_BIG_INTS = false; private static final char[] HEX_CHARS = "0123456789ABCDEF".toCharArray(); private static
     * final BigInteger bi_zero = new BigInteger("0"); private static final BigInteger bi_a2 = new BigInteger(""+a2); private static final BigInteger
     * bi_a3 = new BigInteger(""+a3); private static final BigInteger bi_a4 = new BigInteger(""+a4); private static final BigInteger bi_b2 = new
     * BigInteger(""+b2); private static final BigInteger bi_b3 = new BigInteger(""+b3); private static final BigInteger bi_b4 = new
     * BigInteger(""+b4);
     */

    // change the hash num and you gotta change the hash function below!!!!

    private static final int HASH_NUM = 5;

    private static final int a2 = 2;
    private static final int a3 = 3;
    private static final int a4 = 5;

    private static final int b2 = 51;
    private static final int b3 = 145;
    private static final int b4 = 216;

    public static BloomFilter deserialiseFromMap(Map<String, Object> map) {
        String impl = MapUtils.getMapString(map, "_impl", "");

        if (impl.startsWith(".")) {

            impl = MY_PACKAGE + impl;
        }

        try {
            Class<BloomFilterImpl> cla = (Class<BloomFilterImpl>) Class.forName(impl);

            Constructor<BloomFilterImpl> cons = cla.getDeclaredConstructor(Map.class);

            cons.setAccessible(true);

            return (cons.newInstance(map));

        } catch (Throwable e) {

            Debug.out("Can't construct bloom filter for " + impl, e);

            return (null);
        }
    }

    private int max_entries;
    // private BigInteger bi_max_entries;

    private int entry_count;

    private long start_time = SystemTime.getMonotonousTime();

    public BloomFilterImpl(int _max_entries) {
        // bi_max_entries = new BigInteger( ""+(((_max_entries/2)*2)+1));

        max_entries = ((_max_entries / 2) * 2) + 1;
    }

    public BloomFilterImpl(Map<String, Object> x) {
        max_entries = ((Long) x.get("_max")).intValue();

        entry_count = ((Long) x.get("_count")).intValue();
    }

    protected void serialiseToMap(Map<String, Object> x) {
        String cla = this.getClass().getName();

        if (cla.startsWith(MY_PACKAGE)) {

            cla = cla.substring(MY_PACKAGE.length());
        }

        x.put("_impl", cla);

        x.put("_max", new Long(max_entries));
        x.put("_count", new Long(entry_count));
    }

    public Map<String, Object> serialiseToMap() {
        Map<String, Object> m = new HashMap<String, Object>();

        serialiseToMap(m);

        return (m);
    }

    protected int getMaxEntries() {
        return (max_entries);
    }

    public int add(byte[] value) {
        return (add(bytesToInteger(value)));
    }

    public int remove(byte[] value) {
        return (remove(bytesToInteger(value)));
    }

    public int count(byte[] value) {
        return (count(bytesToInteger(value)));
    }

    public boolean contains(byte[] value) {
        return (contains(bytesToInteger(value)));
    }

    protected int add(int value) {
        int count = 0xffff;

        for (int i = 0; i < HASH_NUM; i++) {

            int index = getHash(i, value);

            // v = value BEFORE inc

            int v = incValue(index);

            if (v < count) {

                count = v;
            }
        }

        if (count == 0) {

            entry_count++;
        }

        // count is the smallest val found *before* incrementing

        return (trimValue(count + 1));
    }

    protected int remove(int value) {
        int count = 0xffff;

        for (int i = 0; i < HASH_NUM; i++) {

            int index = getHash(i, value);

            // v = value BEFORE dec

            int v = decValue(index);

            if (v < count) {

                count = v;
            }
        }

        if (count == 1 && entry_count > 0) {

            entry_count--;
        }

        // count is the value BEFORE dec, decrease one further

        return (trimValue(count - 1));
    }

    protected int count(int value) {
        int count = 0xffff;

        for (int i = 0; i < HASH_NUM; i++) {

            int index = getHash(i, value);

            int v = getValue(index);

            if (v < count) {

                count = v;
            }
        }

        return (count);
    }

    protected boolean contains(int value) {
        for (int i = 0; i < HASH_NUM; i++) {

            int index = getHash(i, value);

            int v = getValue(index);

            if (v == 0) {

                return (false);
            }
        }

        return (true);
    }

    protected abstract int getValue(int index);

    protected abstract int incValue(int index);

    protected abstract int decValue(int index);

    protected abstract int trimValue(int value);

    protected int getHash(int function, int value) {
        long res;

        switch (function) {
            case 0: {
                // x mod p

                res = value;

                break;
            }
            case 1: {
                // x^2 mod p

                res = value * value; // don't try and *fix* this to avoid integer overflow as bloom filters are serialised and this woudl screw up the
                                     // hash...

                break;
            }
            case 2: {
                // bx + a mod p

                res = value * a2 + b2; // as above

                break;
            }
            case 3: {
                // cx + d mod p

                res = value * a3 + b3; // as above

                break;

            }
            case 4: {
                // ex + f mod p

                res = value * a4 + b4; // as above

                break;
            }
            default: {
                System.out.println("**** BloomFilter hash function doesn't exist ****");

                res = 0;
            }
        }

        // System.out.println( "hash[" + function + "] " + value + "->" + r );

        return (Math.abs((int) res % max_entries));
    }

    protected int bytesToInteger(byte[] data) {
        int res = 0x51f7ac81;

        for (int i = 0; i < data.length; i++) {

            // res ^= (data[i]&0xff)<<((i%4)*8);

            res = res * 191 + (data[i] & 0xff);
        }

        return (res);
    }

    /*
     * protected int add( BigInteger value ) { entry_count++; for (int i=0;i<HASH_NUM;i++){ int index = getHash( i, value ); byte v = getValue( index
     * ); if ( v < 15 ){ setValue( index, (byte)(v+1)); } } } public void remove( BigInteger value ) { entry_count--; if ( entry_count < 0 ){
     * entry_count = 0; } for (int i=0;i<HASH_NUM;i++){ int index = getHash( i, value ); byte v = getValue( index ); if ( v > 0 ){ setValue( index,
     * (byte)(v-1)); } } } public boolean contains( BigInteger value ) { for (int i=0;i<HASH_NUM;i++){ int index = getHash( i, value ); int v =
     * getValue( index ); if ( v == 0 ){ return( false ); } } return( true ); } protected int getHash( int function, BigInteger value ) { BigInteger
     * res; switch( function ){ case 0: { // x mod p res = value; break; } case 1: { // x^2 mod p res = value.pow(2); break; } case 2: { // bx + a mod
     * p res = value.multiply( bi_a2 ).add( bi_b2 ); break; } case 3: { // cx + d mod p res = value.multiply( bi_a3 ).add( bi_b3 ); break; } case 4: {
     * // ex + f mod p res = value.multiply( bi_a4 ).add( bi_b4 ); break; } default: { System.out.println(
     * "**** BloomFilter hash function doesn't exist ****" ); res = new BigInteger("0"); } } int r = 0; while(true){ BigInteger x = res.divide(
     * bi_max_entries ); if ( x.compareTo( bi_zero) == 0 ){ r += res.mod( bi_max_entries ).intValue(); break; } r += x.mod( bi_max_entries
     * ).intValue(); res = x; } // System.out.println( "hash[" + function + "] " + value + "->" + r ); return( r % max_entries ); } protected
     * BigInteger bytesToBigInteger( byte[] data ) { StringBuffer buffer = new StringBuffer(data.length*2); for (int i=0;i<data.length;i++){
     * buffer.append( HEX_CHARS[(data[i]>>4)&0x0f] ); buffer.append( HEX_CHARS[data[i]&0x0f] ); } BigInteger res = new BigInteger( new String(buffer),
     * 16 ); return( res ); }
     */

    public int getEntryCount() {
        return (entry_count);
    }

    public int getSize() {
        return (max_entries);
    }

    public void clear() {
        start_time = SystemTime.getMonotonousTime();

        entry_count = 0;
    }

    public long getStartTimeMono() {
        return (start_time);
    }

    protected static byte[] getSerialization(byte[] address, int port) {
        // combine address and port bytes into one
        byte[] full_address = new byte[address.length + 2];
        System.arraycopy(address, 0, full_address, 0, address.length);
        full_address[address.length] = (byte) (port >> 8);
        full_address[address.length + 1] = (byte) (port & 0xff);
        return full_address;
    }

    public String getString() {
        return ("ent=" + entry_count + ",max=" + max_entries);
    }

    public static void main(String[] args) {
        Random rand = new Random();

        /*
         * BloomFilter b1 = new BloomFilterAddRemove8Bit(10000); for (int i=0;i<260;i++){ System.out.println( b1.add( "parp".getBytes()) +
         * ", count = " + b1.count( "parp".getBytes()) + ", ent = " + b1.getEntryCount()); } for (int i=0;i<260;i++){ System.out.println( b1.remove(
         * "parp".getBytes())+ ", count = " + b1.count( "parp".getBytes()) + ", ent = " + b1.getEntryCount()); }
         */

        /*
         * BloomFilter b1 = new BloomFilterAddOnly(90*10/3); byte[] key1 = new byte[4]; for (int i=0;i<200;i++){ if ( i%2==0){ rand.nextBytes( key1 );
         * } b1.add( key1 ); System.out.println( "entries = " + b1.getEntryCount() + ", act = " + i ); } System.exit(0);
         */

        int fp_count = 0;

        for (int j = 0; j < 1000; j++) {

            long start = System.currentTimeMillis();

            BloomFilter b = new BloomFilterAddRemove8Bit(10000);
            // BloomFilter b = new BloomFilterAddOnly(10000);

            int fp = 0;

            for (int i = 0; i < 1000; i++) {

                // String key = "" + rand.nextInt();

                byte[] key = new byte[6];

                rand.nextBytes(key);

                // key = getSerialization( key, 6881 );

                if (i % 2 == 0) {

                    b.add(key);

                    if (!b.contains(key)) {

                        System.out.println("false negative on add!!!!");
                    }
                } else {

                    if (b.contains(key)) {

                        fp++;
                    }
                }

                /*
                 * if ( i%2 == 0 ){ b.remove( key ); if ( b.contains( key )){ System.out.println( "false positive" ); } }
                 */
            }

            System.out.println("" + (System.currentTimeMillis() - start + ", fp = " + fp));

            if (fp > 0) {

                fp_count++;
            }
        }

        System.out.println(fp_count);
    }
}
